package sort

type MergeSort struct {
}

// 归并排序
func (m MergeSort) Sort(nums []int) {
	results := internalMergeSort(nums)
	copy(nums[0:], results[0:])
}

func internalMergeSort(nums []int) []int {
	l := len(nums)
	if l < 2 {
		return nums
	}

	mid := l / 2
	lhs := internalMergeSort(nums[:mid])
	rhs := internalMergeSort(nums[mid:])
	return merge(lhs, rhs)
}

func merge(left []int, right []int) []int {
	newArr := make([]int, len(left)+len(right))
	i, j, index := 0, 0, 0
	for {
		if left[i] > right[j] {
			newArr[index] = right[j]
			index++
			j++
			if len(right) == j {
				copy(newArr[index:], left[i:])
				break
			}

		} else {
			newArr[index] = left[i]
			i++
			index++

			if len(left) == i {
				copy(newArr[index:], right[j:])
				break
			}
		}
	}
	return newArr
}
